package LeetCode;

public class LC_005_LongestPalindromicSubstring_2 {
    public static void main(String[] args) {
        String s = "12332";
        System.out.println(longestPalindrome_dp(s));
    }

    private static String longestPalindrome_dp(String s) {
        if (s.isEmpty() || s.length() <= 1)
            return s;

        String longestStr = null;
        int maxLen = 0;
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = 1;
                longestStr = s.substring(i, i + 2);
                System.out.println(longestStr);
            }
        }

        for (int i = 3; i <= n; i++) {
            for (int j = 0; j <= n - i; j++) {
                int k = j + i - 1;
                if (s.charAt(j) == s.charAt(k)) {
                    dp[j][k] = dp[j + 1][k - 1];
                    if (dp[j][k] == 1 && maxLen < i)
                        longestStr = s.substring(j, k + 1);
                } else {
                    dp[j][k] = 0;
                }
            }
        }
        return longestStr;
    }

}
